Modern data structures may contain huge amounts of data. For example, large networks can have millions or billions of destinations and millions of intermediate nodes, and each node may be identified by its own network address.
Traffic in a network may be routed by looking up records in a routing table or structure. The widely-used Internet Protocol, version 4 (IPv4) uses 32-bit IP addresses and can support up to 232 IP nodes, or about 4 billion addresses. A newer version, IPv6, uses 128-bit IP addresses and can have 2128 IP-addressable nodes. Each record in a data structure might contain one IP address or a range of IP addresses. Routers, switches, and other network nodes may contain a subset of the available IP addresses.
A linear binary search may be used on multiple levels of lookup. Each bit of an input lookup key is used to decide between forks in paths through a tree-like table structure. Since multiple levels of search are required, search time is slow, although the storage space needed for the table is more efficient. A traditional Trie structure has a number of access levels equal to a number of bits in the input key. Each stride, or jump to the next level, consumes one bit of the input key.
A compromise data structure modifies the Trie structure to use strides of more than one bit. This structure can provide a good trade-off between access speed and storage requirements.
FIG. 1 shows prior-art stride tables in a multi-bit Trie structure. Key 18 is the lookup key that is input to the table structure. A lookup is an operation to find an entry in the table structure that matches key 18. Key 18 is divided into four strides S1, S2, S3, S3. In this simplified example, key 18 is only 8 bits wide, and each stride is 2 bits wide.
First stride S1 selects one of four entries in first-level stride table 10. Entries in table 10 contain pointers to tables 12 in the second level. For example, the top second-level table 12 is pointed to by the top entry in table 10, which is selected when S1 is 11. Another second-level table 12′ is pointed to by the third entry in table 10, which is selected when S1 is 01.
Since each stride is 2 bits, each entry in one level points to a table of 4 entries in the next level. Thus a single table 10 in level 1 expands to four tables 12 in the second level, sixteen tables 14 in the third level, and sixty-four tables 16 in the fourth level. A lookup is performed by traversing the four levels of the tables in the table structure. For the example of key 18 having a value of 01110011, the first stride S1 is 01 and selects the third entry in table 10, which points to table 12′ in level 2.
The two stride bits 11 for S2 select from among the four entries in each of tables 12. Since first-level stride table 10 pointed to table 12′, an entry from selected table 12′ is used and other tables 12 are ignored. The top entry in table 12′ is selected by the value (11) of S2. This top entry contains a pointer to selected table 14′ in level 3.
The two stride bits S3 of level three select from among the four entries in selected table 14′ in the third level. The value of S3 is 00, which selects the lowest entry in selected table 14′. This entry has a pointer to one of the 64 tables in level four, selected table 16′.
The value of the fourth stride S4, 11, selects the upper of four entries in selected stride table 16′. This entry contains the result of the lookup, or a pointer to the result. The value 01110011 of key 18 returns this result. Both the key and the result may be composed of several fields that are combined together.
When longest-prefix matches (LPM) are supported, intermediate results may be stored in entries in tables 10, 12, 14 of the intermediate levels, rather than only at the end (leaf) levels.
While such Trie structures modified for multi-bit strides are useful compromises between a fast but large single-level table, and a slow but storage-efficient Trie structure, the storage requirements may still be large using stride tables.
The parent application disclosed using compression functions to compress stride tables. Network tables tend to be sparse tables since the address locations are sparsely populated with valid entries. Most memory locations tend to be empty, or have invalid entries.
Since network tables are sparse, the valid entries in a stride table may be compressed to squeeze out invalid entries and reduce the storage requirements. Ideally, only the valid entries would be stored, but in practice some invalid entries are also stored in the compressed tables. Thus the degree of compression may be less than ideal.
Rather than simply masking or deleting index bits to compress a table, index bits may be compressed using various functions. For example, two or more index bits may be combined together into a single index bit using a logical function such as a logical XOR. A variety of compression functions may be used such as XOR, AND, OR, rotate, shifts, and conditional operations. A field in the table entry can indicate which logical functions to perform for the next level of stride tables. Thus the different logical functions may be mixed together within a table structure to optimize compression.
FIG. 2 shows a logically-compressed stride table as described in more detail in the parent application. Table 20 is a stride table such as one of tables 10, 12, 14, 16 of FIG. 1. In FIG. 2, the current stride size is 4 bits. The current stride of the input key is used as a 4-bit index address that selects one of the 16 entries in stride table 20. Each entry in stride table 20 is in a location identified by a 4-bit index of bits A3, A2, A1, A0. Stride table 20 contains only 4 valid entries, at index locations 1100, 1011, 1001, and 1000. The other 12 indexes contain invalid or empty entries.
Since all four valid entries have a 1 in the most-significant-bit (MSB) of the index, or A3=1, index bit A3 is not needed to select among the four valid entries. Index bit A3 could be removed or masked from stride table 20, as was shown in prior-art FIG. 2. The entries with A3=0 are deleted, since they are all empty entries. Only the entries with A3=1 are retained in compressed stride table 20′.
Further compression can be achieved by combining two of the remaining three index bits to create a new index bit. In this example, index bits A2 and A1 are combined by an XOR function to generate a new A1 index bit. The old A2 and A1 index bits are replaced by this new A1 index bit. The result is that a 2-bit index is used in compressed stride table 22 to select among the 4 entries in table 22.
The size of stride table 22 has been reduced by 75% by masking one index bit (A3) and logically combining two other index bits (A2, A1). Empty entries are removed from compressed stride table 22. Other stride tables could also be compressed, reducing the overall storage requirements.
Two steps were performed to compress the 4 index bits down to 2 index bits. First, one of the index bits (A3) was masked out. Second, two index bits (A2, A1) were logically combined into one index bit (the new A1). The XOR function used for this logical combining is a compression function (CF). Other compression functions may be used for other tables, such as AND, OR, rotate, shift, or more complex functions such as AND-OR, etc.
FIG. 3 shows storing of compression functions (CF) in a stride-table entry. While compression functions could be fixed in hardware or software routines or specified in other ways, storing the compression function in the stride table entry allows different compression functions to be used for different stride tables within the table structure. Thus compression for each table may be optimized, resulting in better overall compression. The compression may even adapt to the type of entries being stored, or to entry changes that occur over time.
Entry 50 is a valid entry in a stride table in level N. Stride bits Sn are extracted from the input key and used to select this entry from other entries in the Nth level of the stride tables. The value of these stride bits Sn are stored in tag field 52 and compared to the input stride bits Sn to ensure a match. Aliasing and other errors are thus avoided.
The number of bits in the next level of the stride table is stored. For example, a value of 0111 could indicate that 8 bits of the input key are used for the stride bits in the next level N+1. In some embodiments, the stride sizes are fixed and next stride size field is not needed.
The compression function (CF) to use for compressing the stride bits to generate the compressed index for the next level N+1 of the stride table is indicated by CF field 60. CF field 60 may include opcode field 62 with a function-type field that indicates the logical function (XOR, shift, etc.). Operand field 64 may contain control bits that control the function, such as indicating a number of positions to shift by, or which bit-positions to use as inputs. A bit mask may be stored in operand field 64. This may be the initial mask (IM) used by an initial masker, or a final mask used by a final masker, or some other mask. The mask may be encoded or compressed in some way, or could be a bit-by-bit mask. Positive or negative masks may be used.
The exact format of CF field 60 may be data-dependent, with some CF functions requiring more control bits than other functions. Opcode field 62 may have a fixed number of bits while operand field 64 varies in width. Decoding of opcode field 62 can determine the number of bits in operand field 64.
Each valid entry 50 in the stride table at level N points to another whole stride table in the next level N+1. Pointer field 58 contains a pointer to the stride table in the next level N+1. The compression function specified in CF field 60 is used to compress the next level stride bits SN+1 to find the entry in the next-level stride table pointed to by pointer field 58. Pointer field 58 could contain a full address or a partial address, offset, or some other way of indicating the next stride table.
The final level of stride tables does not point to another level. Instead, pointer field 56 contains a pointer to a lookup result, or could contain the result itself. Some fields may be optional for some kinds of entries. Sometimes, a partial lookup is performed. There may be some valid entries for which only some of the input key's bits are matched; other input key bits are ignored (don't cares). These are referred to as regional entries. For example, the 15 most-significant-bits (MSB's) of a key are matched while the remaining 17 LSB's are ignored. When the first and second level strides are each 8 bits wide, then the second-level stride only matches 7 of the 8 stride bits. For some lookups, such as longest-prefix matches (LPM), both result pointer field 56 and next-level pointer field 58 may be valid. When both pointers are valid, then result pointer field 56 indicates the result when no more-precise match is found.
MSB-to-use field 54 indicates that only the 7 MSB's of the 8 stride bits are matched when comparing tag field 52 to the input key. For a regional entry in the database, it is possible to successfully terminate the search prior to completely traversing all of the levels. A match may be identified prior to traversing all of the levels. This may occur when a search key matches a regional entry, and there is no exact match entry present for a given search key. In this case, there is a valid result available even prior to completing traversal. In this case the result may be provided in field 56.
While using compression functions to reduce the sizes of stride tables is useful, the input key that is divided into strides is sometimes quite long. Input keys of 500 bits or more may occur in some applications, such as for IPv6 networks. These extremely long keys may require many strides, or may require long strides. For example, a 512-bit key could be divided into 64 strides of 8-bits per stride, or into 8 strides of 64-bits per stride. Neither option is desirable, resulting in too many levels of stride tables, or in excessively large stride tables. What is desired is a multi-stride lookup structure that uses a more compressed input key to increase efficiency, and to reduce a number of levels of stride tables needed. Efficient memory management is further desired for stride tables and associated structures.